InforLorV4, Main, Exploration, bibRecord, 00BC30

On the complexity of unification and disunification in commutative idempotent semigroups

Identifieur interne : 00BC30 ( Main/Exploration ); précédent : 00BC29; suivant : 00BC31

On the complexity of unification and disunification in commutative idempotent semigroups

Auteurs : Miki Hermann [France] ; Phokion G. Kolaitis [États-Unis]

Source :

Lecture Notes in Computer Science [ 0302-9743 ]

RBID : ISTEX:8EB5521B4CAAB602673655DD72DD512B6F24A1B7

Descripteurs français

Pascal (Inist)
- Complexité calcul, Informatique théorique, Programmation logique, Théorie équationnelle, Unification.

English descriptors

KwdEn :
- Computational complexity, Computer theory, Equational theory, Logical programming, Unification.

Abstract

Abstract: We analyze the computational complexity of elementary unification and disunification problems for the equational theory ACI of commutative idempotent semigroups. From earlier work, it was known that the decision problem for elementary ACI-unification is solvable in polynomial time. We show that this problem is inherently sequential by establishing that it is complete for polynomial time (P-complete) via logarithmic-space reductions. We also investigate the decision problem and the counting problem for elementary ACI-matching and observe that the former is solvable in logarithmic space, but the latter is #P-complete. After this, we analyze the computational complexity of the decision problem for elementary ground ACI-disunification. Finally, we study the computational complexity of a restricted version of elementary ACI-matching, which arises naturally as a set-term matching problem in the context of the logic data language LDL. In both cases, we delineate the boundary between polynomial-time solvability and NP-hardness by taking into account two parameters, the number of free constants and the number of disequations or equations.

Url:

https://api.istex.fr/ark:/67375/HCB-LN96X5SZ-N/fulltext.pdf

DOI: 10.1007/BFb0017446

Affiliations:

Le document en format XML

<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">On the complexity of unification and disunification in commutative idempotent semigroups</title>
<author><name sortKey="Hermann, Miki" sort="Hermann, Miki" uniqKey="Hermann M" first="Miki" last="Hermann">Miki Hermann</name>
</author>
<author><name sortKey="Kolaitis, Phokion G" sort="Kolaitis, Phokion G" uniqKey="Kolaitis P" first="Phokion G." last="Kolaitis">Phokion G. Kolaitis</name>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:8EB5521B4CAAB602673655DD72DD512B6F24A1B7</idno>
<date when="1997" year="1997">1997</date>
<idno type="doi">10.1007/BFb0017446</idno>
<idno type="url">https://api.istex.fr/ark:/67375/HCB-LN96X5SZ-N/fulltext.pdf</idno>
<idno type="wicri:Area/Istex/Corpus">002112</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">002112</idno>
<idno type="wicri:Area/Istex/Curation">002084</idno>
<idno type="wicri:Area/Istex/Checkpoint">002763</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">002763</idno>
<idno type="wicri:doubleKey">0302-9743:1997:Hermann M:on:the:complexity</idno>
<idno type="wicri:Area/Main/Merge">00C408</idno>
<idno type="wicri:source">INIST</idno>
<idno type="RBID">Pascal:98-0011360</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">000C19</idno>
<idno type="wicri:Area/PascalFrancis/Curation">000C55</idno>
<idno type="wicri:Area/PascalFrancis/Checkpoint">000C19</idno>
<idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000C19</idno>
<idno type="wicri:doubleKey">0302-9743:1997:Hermann M:on:the:complexity</idno>
<idno type="wicri:Area/Main/Merge">00C516</idno>
<idno type="wicri:Area/Main/Curation">00BC30</idno>
<idno type="wicri:Area/Main/Exploration">00BC30</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">On the complexity of unification and disunification in commutative idempotent semigroups</title>
<author><name sortKey="Hermann, Miki" sort="Hermann, Miki" uniqKey="Hermann M" first="Miki" last="Hermann">Miki Hermann</name>
<affiliation wicri:level="3"><country xml:lang="fr">France</country>
<wicri:regionArea>LORIA (CNRS), BP 239, 54506, Vandceuvre-lés-Nancy</wicri:regionArea>
<placeName><region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
<settlement type="city">Vandceuvre-lés-Nancy</settlement>
</placeName>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">France</country>
</affiliation>
</author>
<author><name sortKey="Kolaitis, Phokion G" sort="Kolaitis, Phokion G" uniqKey="Kolaitis P" first="Phokion G." last="Kolaitis">Phokion G. Kolaitis</name>
<affiliation wicri:level="2"><country xml:lang="fr">États-Unis</country>
<wicri:regionArea>Computer Science Department, University of California, 95064, Santa Cruz, CA</wicri:regionArea>
<placeName><region type="state">Californie</region>
</placeName>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">États-Unis</country>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="s" type="main" xml:lang="en">Lecture Notes in Computer Science</title>
<title level="s" type="abbrev">Lect Notes Comput Sci</title>
<idno type="ISSN">0302-9743</idno>
<idno type="eISSN">1611-3349</idno>
<idno type="ISSN">0302-9743</idno>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><idno type="ISSN">0302-9743</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Computational complexity</term>
<term>Computer theory</term>
<term>Equational theory</term>
<term>Logical programming</term>
<term>Unification</term>
</keywords>
<keywords scheme="Pascal" xml:lang="fr"><term>Complexité calcul</term>
<term>Informatique théorique</term>
<term>Programmation logique</term>
<term>Théorie équationnelle</term>
<term>Unification</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Abstract: We analyze the computational complexity of elementary unification and disunification problems for the equational theory ACI of commutative idempotent semigroups. From earlier work, it was known that the decision problem for elementary ACI-unification is solvable in polynomial time. We show that this problem is inherently sequential by establishing that it is complete for polynomial time (P-complete) via logarithmic-space reductions. We also investigate the decision problem and the counting problem for elementary ACI-matching and observe that the former is solvable in logarithmic space, but the latter is #P-complete. After this, we analyze the computational complexity of the decision problem for elementary ground ACI-disunification. Finally, we study the computational complexity of a restricted version of elementary ACI-matching, which arises naturally as a set-term matching problem in the context of the logic data language LDL. In both cases, we delineate the boundary between polynomial-time solvability and NP-hardness by taking into account two parameters, the number of free constants and the number of disequations or equations.</div>
</front>
</TEI>
<affiliations><list><country><li>France</li>
<li>États-Unis</li>
</country>
<region><li>Californie</li>
<li>Grand Est</li>
<li>Lorraine (région)</li>
</region>
<settlement><li>Vandceuvre-lés-Nancy</li>
</settlement>
</list>
<tree><country name="France"><region name="Grand Est"><name sortKey="Hermann, Miki" sort="Hermann, Miki" uniqKey="Hermann M" first="Miki" last="Hermann">Miki Hermann</name>
</region>
<name sortKey="Hermann, Miki" sort="Hermann, Miki" uniqKey="Hermann M" first="Miki" last="Hermann">Miki Hermann</name>
</country>
<country name="États-Unis"><region name="Californie"><name sortKey="Kolaitis, Phokion G" sort="Kolaitis, Phokion G" uniqKey="Kolaitis P" first="Phokion G." last="Kolaitis">Phokion G. Kolaitis</name>
</region>
<name sortKey="Kolaitis, Phokion G" sort="Kolaitis, Phokion G" uniqKey="Kolaitis P" first="Phokion G." last="Kolaitis">Phokion G. Kolaitis</name>
</country>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 00BC30 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 00BC30 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Lorraine
   |area=    InforLorV4
   |flux=    Main
   |étape=   Exploration
   |type=    RBID
   |clé=     ISTEX:8EB5521B4CAAB602673655DD72DD512B6F24A1B7
   |texte=   On the complexity of unification and disunification in commutative idempotent semigroups
}}

This area was generated with Dilib version V0.6.33.
Data generation: Mon Jun 10 21:56:28 2019. Site generation: Fri Feb 25 15:29:27 2022

Serveur d'exploration sur la recherche en informatique en Lorraine

On the complexity of unification and disunification in commutative idempotent semigroups

On the complexity of unification and disunification in commutative idempotent semigroups

Source :

Descripteurs français

English descriptors

Abstract

Links toward previous steps (curation, corpus...)

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri

	Serveur d'exploration sur la recherche en informatique en Lorraine
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.